public class Solution {
    public int movingCount(int m, int n, int k) {
        int[][] arr = new int[m][n];
        return recur(arr, 0, 0, k);
    }

    private int recur(int[][] arr, int i, int j, int k) {
        if (i < 0 || j < 0 || i >= arr.length || j >= arr[0].length
                || sum(i) + sum(j) > k
                || arr[i][j] == 1) return 0;
        arr[i][j] = 1;
        return recur(arr, i + 1, j, k) +
                recur(arr, i, j + 1, k) +
                recur(arr, i - 1, j, k) +
                recur(arr, i, j - 1, k) + 1;
    }

    private int sum(int i) {
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i = i / 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.sum(12345));
        System.out.println(s.movingCount(3, 1, 0));
    }
}
